package com.lun.swordtowardoffer2.c05;

import java.util.List;

public class FindMinDifference {
	
	private static final int NUM_OF_MINUTES_IN_A_DAY = 24 * 60;

	public int findMinDifference(List<String> timePoints) {
		
		if(timePoints.size() > NUM_OF_MINUTES_IN_A_DAY)//有重复的，间隔为0
			return 0;
		
		boolean[] minuteFlags = new boolean[NUM_OF_MINUTES_IN_A_DAY];
		
		for(String str : timePoints) {
			
			String[] time = str.split(":");
			int min = Integer.valueOf(time[0]) * 60 + Integer.valueOf(time[1]);
			
			if(minuteFlags[min]) //重复时间点
				return 0;
			
			minuteFlags[min] = true;
		}
		
		//正片开始
		int minDiff = NUM_OF_MINUTES_IN_A_DAY;//= 第一天00:00 - 第二天00:00
		int prev = -1, first = NUM_OF_MINUTES_IN_A_DAY - 1, last = -1;
		
		for(int i = 0; i < NUM_OF_MINUTES_IN_A_DAY; i++) {
			if(!minuteFlags[i]) continue;
			
			if(prev > 0)
				minDiff = Math.min(minDiff, i - prev);
			
			prev = i;
			first = Math.min(first, i);
			last = Math.max(last, i);
		}
		
		//最后，还要考虑首尾连接情况，联想时钟为何通常是圆，如 第一天的23:45 与 第二天的00:03。
		return Math.min(minDiff, first + NUM_OF_MINUTES_IN_A_DAY - last);
	}
	
}
